/*
 * File:   DivideAndConquer.cpp
 * Author: jd219546
 *
 * Created on 17 octobre 2011, 18:02
 */

#include "DivideAndConquer.h"
#include "Kadane.h"

#include "Perfs.h"
#include <omp.h>

#include <algorithm>

#define DISPLAY 0


DivideAndConquer::DivideAndConquer(int max_recursivity):data_ptr(0),max_recursivity(max_recursivity)
,each_thread_result(omp_get_max_threads())
{
#if DISPLAY
cout << "Constructing a Divide and Conquer solver with recursivity = " << max_recursivity << endl;
#endif

#pragma omp parallel
{
    each_thread_result[omp_get_thread_num()].sum = 1 << 31;
}

}


DivideAndConquer::~DivideAndConquer() {
}

inline
void DivideAndConquer::update_result(Result & result, t_int x0, t_int y0, t_int x1, t_int y1, t_int sum)
{
    result.x0 = x0;
    result.y0 = y0;
    result.x1 = x1;
    result.y1 = y1;
    result.sum = sum;
}

inline
void  DivideAndConquer::recursive_divide_and_conquer(int recursivity_level, s_rect rect)
{
	 /*        distx
      *===================
      |
disty |
      |
      */
    //cout << "Best result so far" << endl;
    //result.display();
    int distx = rect.x1 - rect.x0 + 1;
    int disty = rect.y1 - rect.y0 + 1;
    //cout << "working on " << rect.x0 << "," <<
    //rect.y0 << " to " << rect.x1 << "," << rect.y1 << " and distx = " << distx
    //<< " and disty = " << disty << endl;
    if (max_recursivity > recursivity_level && ( distx > 1 || disty > 1))
    {
        //slicing the problem

        if (disty > distx)
        {
			int midy = rect.y0 + disty/2 - 1;
			//if more rows than columns : slice along mid row
	 /*        distx
(x0,y0)===================
      |      upper
disty |____________________  central row     <-y0+midy/2
      |      lower
      *                    (x1,y1)
      */
			//solve upper problem
            s_rect upper_rect = rect;
            upper_rect.y1 = midy;
            recursive_divide_and_conquer(recursivity_level+1, upper_rect);
			//solve lower problem
			s_rect lower_rect = rect;
			lower_rect.y0 = midy + 1;
			recursive_divide_and_conquer(recursivity_level+1, lower_rect);
			//solve central row problem
            this->command_queue.push_back(new CentralRowCommand(rect, midy));



		}
		else
		{
			//else : slice along mid column
	 /*        distx
(x0,y0)===================
      |       |
disty |   left|right
      |       |
      *    x0+midx             (x1,y1)
      */
      int midx = rect.x0 + distx/2 - 1;
			//solve left problem
			s_rect left_rect = rect;
			left_rect.x1 = midx;
			recursive_divide_and_conquer(recursivity_level+1, left_rect);
			//solve right problem
			s_rect right_rect = rect;
			right_rect.x0 = midx + 1;
			recursive_divide_and_conquer( recursivity_level+1, right_rect);
			//solve central column problem
			//central_col_solver.solve_MCS(data_ptr,res,rect,midx);
            this->command_queue.push_back(new CentralColCommand(rect, midx));
		}
    }
    else
    {
    	//cout << "Kadane on rect : " << rect.x0 << "," << rect.y0 << " to " << rect.x1 << "," << rect.y1 << endl;
        this->command_queue.push_back(new KadaneCommand(rect));
    }
}

bool sort_command_pointers(const Command * cmd1, const Command * cmd2)
{
    return cmd1->workload < cmd2->workload;
}

void DivideAndConquer::solve_MCS(const Data& data, Result& result)
{
    this->data_ptr = &data;
    update_result(result, 0,0,0,0,data.getElt(0,0));//.x0 = result.y0 = 0;
    int recursivity_level = 0;
    s_rect rect;
    rect.x0 = rect.y0 = 0;
    rect.x1 = data.getColumns()-1;
    rect.y1 = data.getRows()-1;
    /*
    //Central col : (0,0) to (3999,3999) with central col = 1999
    central_col_solver.solve_MCS(&data,result,rect,1999);
    //Central row : (2000,0) to (3999,3999) with central row = 1999
    rect.x0 = 2000;
    central_row_solver.solve_MCS(&data,result,rect,1999);
    rect.x0 = 0;
    rect.y1 = 3999;
    rect.x1 = 1999;
    central_row_solver.solve_MCS(&data,result,rect,1999);
    return;
    */

    recursive_divide_and_conquer(recursivity_level, rect);
    sort(this->command_queue.begin(), this->command_queue.end(), sort_command_pointers);
    //Command * tmp = command_queue[2];
    //command_queue[2] = command_queue[4];
    //command_queue[4] = tmp;
    Result best_result;
    best_result.sum = 1 << 31;
    vector<double> execution_times(command_queue.size());
    #pragma omp parallel for schedule(static,1)
    for(t_uint i = 0 ; i < command_queue.size() ; i++)
    {
            //cout << "Executing command " << i <<  ": " << command_queue[i]->name() << endl;
            double startin = Perfs::my_gettimeofday();
            const Result & res = command_queue[i]->solve_MCS(data);
            double endin = Perfs::my_gettimeofday();
            execution_times[i] = endin - startin;
            //res.display();
#pragma omp critical
            {
            if (res > best_result)
                best_result = res;
            }

    }

#if DISPLAY
    for (t_uint i = 0 ; i < execution_times.size() ; i++)
    {
        cout << "execution times of command " << i << " " << command_queue[i]->name() <<
        " : " << execution_times[i] << " s" << endl;]
        delete command_queue[i];
    }
#endif // DISPLAY
    result = best_result;
    //cout << "Final result = " << endl;
    //result.display();
}
